# 初始化节点，具有数据和指向下一个节点的属性
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


# 列表类，定义长度和列表的头
class List:
    def __init__(self):
        self.head = Node()
        self.length = 0

    def insert(self, pos, data):
        # 插入节点位置长度为当前节点长度
        assert pos in range(0, self.length+1)
        # 找到在其之后插入节点的当前节点
        tmp_ptr = self.head
        while pos > 0:
            tmp_ptr = tmp_ptr.next
            pos -= 1
        # 插入操作
        new_node = Node()
        new_node.data = data
        new_node.next = tmp_ptr.next
        tmp_ptr.next = new_node
        self.length += 1

    # 增加
    def append(self, data):
        self.insert(self.length, data)

    # 修改数据
    def update(self, pos, data):
        # 修改的长度为当前节点的长度，所有范围内可改
        assert pos in range(0, self.length)
        # 找到当前可修改的节点的位置
        tmp_ptr = self.head
        while pos > 0:
            tmp_ptr = tmp_ptr.next
            pos -= 1
        # 数据替换
        tmp_ptr.data = data

    # 删除，根据位置
    def remove(self, pos):
        assert pos in range(0, self.length)
        tmp_ptr = self.head
        while pos > 0:
            tmp_ptr = tmp_ptr.next
            pos -= 1
        if tmp_ptr.next is not None:
            del_node = tmp_ptr.next
            tmp_ptr.next = del_node.next
            self.length -= 1

    # 根据数据删除
    def pop(self, data):
        tmp_ptr = self.head
        len = 0
        while len < self.length:
            # 找到要删除的节点的上一节点
            tmp_ptr = tmp_ptr.next
            if tmp_ptr.data == data:
               self.remove(len)
            len += 1

    # 遍历
    def traversal(self):
        tmp_ptr = self.head.next
        while tmp_ptr is not None:
            yield tmp_ptr.data
            tmp_ptr = tmp_ptr.next


def line():
    print()
    print('=========================')


if __name__ == "__main__":
    l = List()
    l.append("a")
    l.append(2)
    l.append(3)

    for m in l.traversal():
        print(m, end=' ')
    line()

    l.insert(3, 4)
    for m in l.traversal():
        print(m, end=' ')
    line()

    l.update(1, 10)
    for m in l.traversal():
        print(m, end=' ')
    line()

    l.remove(3)
    for m in l.traversal():
        print(m, end=' ')
    line()

    l.pop(10)
    for m in l.traversal():
        print(m, end=' ')

